# class Solution(object):
#     def countSmaller(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[int]
#         """
#         import bisect
#         ans=[]
#         tmp = []
#         for i in reversed(nums):
#             pos = bisect.bisect_left(tmp, i)# 返回插入i左边数值的个数
#             ans.append(pos)
#             tmp.insert(pos, i)
#         return list(reversed(ans))
class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def sort(enum):
            half = len(enum)//2
            if half :
                left = sort(enum[:half])
                right =sort(enum[half:])
                for i in range(len(enum)-1,-1,-1):
                    if not right or left and left[-1][1]>right[-1][1]:
                        # 保证左边有值，如果左边没值而右边有值就会执行else
                        # (not right) or (left and left[-1][1]>right[-1][1])
                        smaller[left[-1][0]] += len(right)
                        enum[i] = left[-1]
                        left.pop()
                    else:
                        enum[i] = right[-1]
                        right.pop()
            return enum
        smaller= [0]*len(nums)
        sort(list(enumerate(nums)))
        return smaller